package org.regotto.basics.sort;

import org.regotto.common.Data;
import org.regotto.common.Utils;

public class QuickSort {


    public static void main(String[] args) {
        int[] q = Data.getInts(false);
        qs(q, 0, q.length - 1);
        for (int i = 0; i < q.length; i++) System.out.print(q[i] + " ");
    }

    public static void qs(int[] q, int l, int r) {
        if (l >= r) return;
        int m = q[(l + r) / 2], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (q[i] < m);
            do j--; while (q[j] > m);
            if (i < j) Utils.swap(q, i, j);
        }
        qs(q, l, j);
        qs(q, j + 1, r);
    }

}
